Robert Kleinberg
Abstract:
The resilience of networks to various types of failures is an undercurrent in many parts of graph theory and network algorithms. In this paper we study the resilience of networks in the presence of cascading failures — failures that spread from one node to another across the network structure. One finds such cascading processes at work in the kind of contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease.
A widely studied model of cascades in networks assumes that each node of the network has an integer threshold specifying the number of its neighbors that must fail in order for it to fail. We assume that each node selects a threshold independently using a specified probability distribution. Our work centers on the maximum failure probability of any node in the graph. It turns out that when selecting among a set of graphs to minimize this probability, the result depends quite intricately on the distribution of thresholds. We develop several techniques for minimizing the maximum failure probability among d-regular graphs. For d=2 we are able to solve the problem completely: the optimal graph is always a clique (i.e. triangle) or tree (i.e. infinite path), although which graph is better exhibits a surprising non-monotonicity as the threshold parameters vary. When d is greater than 2 we present a technique based on power-series expansions of the failure probability that allows us to compare graphs in certain parts of the parameter space, deriving conclusions including the fact that as the threshold distribution varies, at least three different graphs are optimal among d-regular graphs. In particular, the set of optimal graphs here includes one which is neither a clique nor a tree.
This is joint work with Larry Blume, David Easley, Jon Kleinberg, and Eva Tardos.